package com.spirng.leetcode.day08;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test39 {
    public static void main(String[] args) {
        Test39 test39 = new Test39();
        test39.combinationSum(new int[]{2,3,6,7},7);
    }
    int sum=0;
    LinkedList list=new LinkedList<Integer>();
    ArrayList<List<Integer>> lists=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates,target,0,sum);
        return lists;
    }
    public void backtracking(int [] candidates,int target,int offSize,int sum){
        if(target-sum==1){
            return;
        }
        if(sum>target){
            return;
        }
        if(sum==target){
            lists.add(new ArrayList<>(list));
            return;
        }
        if(offSize==candidates.length){
            return;
        }
        for (int i = offSize; i < candidates.length; i++) {
            list.add(candidates[i]);
            backtracking(candidates,target,i,sum+candidates[i]);
            list.removeLast();
        }
    }
}
